package org.example.Soution002;

import java.util.*;

public class RottingOrange {
    public static void main(String[] args) {
        RottingOrange orange = new RottingOrange();
//        int[][] grid={{2,1,1},{1,1,1},{0,1,2}};
//        int[][] grid={
//                {2,0,1,1,1,1,1,1,1,1},
//                {1,0,1,0,0,0,0,0,0,1},
//                {1,0,1,0,1,1,1,1,0,1},
//                {1,0,1,0,1,0,0,1,0,1},
//                {1,0,1,0,1,0,0,1,0,1},
//                {1,0,1,0,1,1,0,1,0,1},
//                {1,0,1,0,0,0,0,1,0,1},
//                {1,0,1,1,1,1,1,1,0,1},
//                {1,0,0,0,0,0,0,0,0,1},
//                {1,1,1,1,1,1,1,1,1,1}
//        };
        int[][] grid={{0,1,1,2,1,1,1}};
        System.out.println(orange.orangesRotting(grid));
    }


    int good=0;
    int time=-1;
    Deque<List<Integer>> q=new LinkedList<>();
    public int orangesRotting(int[][] grid) {
        for(int i=0;i<grid.length;i++){
            for(int j=0;j<grid[0].length;j++){
                //仅处理有橘子的地方
                if(grid[i][j]==1) good++;
                //开始腐化
                if(grid[i][j]==2){
                    List<Integer> temp=new ArrayList<>();
                    temp.add(i); temp.add(j);
                    q.add(temp);
                }
            }
        }
        if(q.size()==0&&good==0) return 0;
        rottenOrg(grid);
        return good==0?time:-1;
    }

    public void rottenOrg(int[][] grid) {
        if(q.size()==0) return;
        int wide=grid[0].length;
        int high=grid.length;
        int flag=q.getLast().get(0)*wide+q.getLast().get(1)+1;
        while(!q.isEmpty()){
            List<Integer> temp=q.pollFirst();
            if(temp.get(0)-1>=0&&grid[temp.get(0)-1][temp.get(1)]==1){
                List<Integer> tempUp=new ArrayList<>();
                tempUp.add(temp.get(0)-1);tempUp.add(temp.get(1));
                q.add(tempUp);
                grid[temp.get(0)-1][temp.get(1)]=2;
                good--;
            }
            if(temp.get(1)-1>=0&&grid[temp.get(0)][temp.get(1)-1]==1){
                List<Integer> tempLeft=new ArrayList<>();
                tempLeft.add(temp.get(0));tempLeft.add(temp.get(1)-1);
                q.add(new ArrayList<>(tempLeft));
                grid[temp.get(0)][temp.get(1)-1]=2;
                good--;
            }
            if(temp.get(1)+1<wide&&grid[temp.get(0)][temp.get(1)+1]==1){
                List<Integer> tempRight=new ArrayList<>();
                tempRight.add(temp.get(0));tempRight.add(temp.get(1)+1);
                q.add(new ArrayList<>(tempRight));
                grid[temp.get(0)][temp.get(1)+1]=2;
                good--;
            }
            if(temp.get(0)+1<high&&grid[temp.get(0)+1][temp.get(1)]==1){
                List<Integer> tempDown=new ArrayList<>();
                tempDown.add(temp.get(0)+1);tempDown.add(temp.get(1));
                q.add(new ArrayList<>(tempDown));
                grid[temp.get(0)+1][temp.get(1)]=2;
                good--;
            }
            if((temp.get(0)*wide+temp.get(1)+1)==flag){
                time++;
                if(!q.isEmpty()){
                    flag=q.getLast().get(0)*wide+q.getLast().get(1)+1;
                }
            }
        }
    }
}
